/*
Main program for the virtual memory project.
Make all of your modifications to this file.
You may add or rearrange any code or data as you need.
The header files page_table.h and disk.h explain
how to use the page table and disk interfaces.
*/

#include "page_table.h"
#include "disk.h"
#include "program.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include <sys/queue.h>
#define SFIFO_RATIO 0.25
#define CUSTOM_RATIO 0.40


//******************************GLOBAL VARIABLES******************************
int num_page_faults = 0; // number of page faults encountered
int num_disk_reads = 0; // number of times the disk was read for the algorithm
int wrt_cnt = 0; // number of times the disk was written to for the algorithm

// size and length of two busy queues in 2fifo
int l1_nframes; // number of frames that can be in list1
int l1_len; // number of frames currently in list1
int l2_nframes; // number of frames that can be in list2
int l2_len; // number of frames currently in list2

// an array of all pages for 2fifo and whether or not they have been written
// 0 if not written, 1 if written
int* wbit;

// the free list
struct free_frame {
	int num; // the frame number
	TAILQ_ENTRY(free_frame) entries; // the next element
};
// the busy list for fifo
struct busy_frame {
	int num; // the frame number
	TAILQ_ENTRY(busy_frame) entries; // then next element
};

// replacement algorithm pointer type, return the page to kick out
typedef int (*replace_t) ( struct page_table * pt, int page );

// the head of free list
TAILQ_HEAD(, free_frame) free_list_head;
// the head of busy list
TAILQ_HEAD(, busy_frame) busy_list_head;
// the second busy list used by the second fifo algorithm
TAILQ_HEAD(, busy_frame) sbusy_list_head;

// the pointer to replacement function
replace_t replace_func;

// an inverted table for page table
int* inv_pg_tb;
//typedef struct page_table page_table_t;
struct disk * mydisk;


//************************************CODE************************************

// prints the 2 lists for 2fifo and custom
void print_list()
{
	struct busy_frame * item; // each frame in the list
	printf("first list len %d\n", l1_len);
	TAILQ_FOREACH(item, &busy_list_head, entries) {
		printf("%d ", item->num);
	}
	printf("\n");
	printf("second list len %d\n", l2_len);
	TAILQ_FOREACH(item, &sbusy_list_head, entries) {
		printf("%d ", item->num);
	}
	printf("\n");
}

// finds which page to replace using the fifo algorithm and replaces it with
// the page indicated
// Parameter pt: the page table
// Parameter page: the page we want to put in memory
// Return: the page replaced
int fifo_replace(struct page_table *pt,int page)
{
	int rep_frame; // frame to work on

	// Get physmem
	char* myPM = page_table_get_physmem(pt); // physical memory

	// if free list is empty, need to use fifo to find replacememt frame
	if(TAILQ_EMPTY(&free_list_head)){
		struct busy_frame* choice; // the frame to kick out
		struct busy_frame* insert; // the frame to put in the queue

		// dequeue the busy queue
		choice = TAILQ_FIRST(&busy_list_head);
		TAILQ_REMOVE(&busy_list_head, choice, entries);
		rep_frame = choice -> num;
		free(choice);

		// enqueue
		insert = malloc(sizeof(*insert));
		if(insert == NULL) {
			perror("malloc failed");
			exit(EXIT_FAILURE);
		}
		insert -> num = rep_frame;
		TAILQ_INSERT_TAIL(&busy_list_head, insert, entries);

		// Check the bits for page to kick out
		int rep_bits; // the bits of the frame to replace
		page_table_get_entry(pt, inv_pg_tb[rep_frame], &rep_frame, &rep_bits);

		// write page to disk if dirty
		if(rep_bits == (PROT_READ|PROT_WRITE)) {
			wrt_cnt ++;
			disk_write(mydisk, inv_pg_tb[rep_frame], &myPM[rep_frame * (PAGE_SIZE)]);
		}

		// change the page table for the evicted page
		page_table_set_entry(pt, inv_pg_tb[rep_frame], 0, PROT_NONE);
	}
	else{
		// there's free frame, get it and insert it into busy list
		struct free_frame * fitem; // the free frame
		fitem = TAILQ_FIRST(&free_list_head);
		TAILQ_REMOVE(&free_list_head, fitem, entries);
		rep_frame = fitem->num;
		free(fitem);

		// update the busy list info at initialization
		struct busy_frame * bitem; // the frame that we are putting in the queue
		bitem = malloc(sizeof(*bitem));
		if (bitem == NULL) {
			perror("malloc failed");
			exit(EXIT_FAILURE);
		}
		bitem -> num = rep_frame;
		TAILQ_INSERT_TAIL(&busy_list_head, bitem, entries);

	}   

	// read new page from disk into new frame
	disk_read(mydisk, page, &myPM[rep_frame * (PAGE_SIZE)]);
	num_disk_reads++;

	// change page table for current page to the new frame
	page_table_set_entry(pt, page, rep_frame, PROT_READ);
	inv_pg_tb[rep_frame] = page;

	return rep_frame;
}

// insert an item into 2fifo 2 queues return a frame to kick out
// Parameter pt: the page table
// Parameter inframe: the frame to insert
// Return: the frame kicked out of list2, if any. Otherwise returns -1.
int sfifo_insert(struct page_table *pt, int inframe)
{
	// insert into list1
	struct busy_frame * bitem; // the frame to insert into list1
	bitem = malloc(sizeof(*bitem));
	if (bitem == NULL) {
		perror("malloc failed");
		exit(EXIT_FAILURE);
	}
	bitem -> num = inframe;
	TAILQ_INSERT_TAIL(&busy_list_head, bitem, entries);
	// update the busy list info at initialization
	if(l1_len < l1_nframes){
		l1_len ++;
		return -1;
	}
	bitem = TAILQ_FIRST(&busy_list_head);
	TAILQ_REMOVE(&busy_list_head, bitem, entries);

	// Clear bits for frame from list1 to list2
	int midframe; // frame that is being moved from list1 to list2
	midframe = bitem -> num;
	int midpage; // page that is being moved
	midpage = inv_pg_tb[midframe];

	// get current bits for the page
	int frame; // the frame that is being moved
	int bits; // the bits of the frame that is being moved
	page_table_get_entry(pt, midpage, &frame, &bits);

	// save wbit table for the second page
	wbit[midpage] = bits;

	// change bits to none, but keep the frame
	page_table_set_entry(pt, midpage, midframe, PROT_NONE);

	// insert into list2
	TAILQ_INSERT_TAIL(&sbusy_list_head, bitem, entries);
	if(l2_len < l2_nframes){
		l2_len ++;
		return -1;
	}
	bitem = TAILQ_FIRST(&sbusy_list_head);
	TAILQ_REMOVE(&sbusy_list_head, bitem, entries);

	int outframe; // the frame number to kick out
	outframe = bitem -> num;
	char* myPM = page_table_get_physmem(pt); // physical memory
	if (wbit[inv_pg_tb[outframe]] == (PROT_READ|PROT_WRITE)) {
		wrt_cnt ++;
		disk_write(mydisk, inv_pg_tb[outframe], &myPM[outframe * (PAGE_SIZE)]);
	}
	wbit[inv_pg_tb[outframe]] = PROT_NONE;
	free(bitem);
	return outframe;
}

// Looks for the page in list2 and if it finds it, reenables bits and puts
// in list1
// Parameter pt: the page table
// Parameter page: the page that we want to look for
// Return: if found the page, returns the page itself, else returns -1
int trans_two2one(struct page_table *pt, int page)
{
	struct busy_frame *list2_item; // frame to move, if found
	struct busy_frame *tmp_item; // temp item
	int frame; // the frame to search list2 for
	int bits; // the bits from page_table_get_entry

	page_table_get_entry(pt, page, &frame, &bits);

	for (list2_item = TAILQ_FIRST(&sbusy_list_head); list2_item != NULL;
			list2_item = tmp_item)
	{
		tmp_item = TAILQ_NEXT(list2_item, entries);
		if((frame != 0 && list2_item -> num == frame) || 
				(list2_item->num == 0 && inv_pg_tb[0] == page))
		{
			// remove the item from list2
			TAILQ_REMOVE(&sbusy_list_head, list2_item, entries);
			l2_len --;

			// resume the sec list frame page bits bits
			page_table_set_entry(pt, page, frame, wbit[page]);
			// insert that frame into list1
			sfifo_insert(pt, frame);
			free(list2_item);
			return(page);
		}
	}

	// if not in list2, return -1
	return(-1);
}

// first looks in list2 and moves to list1 if found, otherwise insert the frame
// into the list1 and if we get a frame out of list2, then we use that to
// replace
// Parameter pt: the page table
// Parameter page: the page that we want to find a frame for
// Return: the frame replaced if we replaced it, otherwise return -1
int sfifo_replace(struct page_table *pt,int page)
{
	//print_list(); 
	if(trans_two2one(pt, page) >= 0) return(-1);

	// for the rest of this function, we know that the frame is not in list2

	int rep_frame; // frame to work on, if page is not in second list
	char* myPM = page_table_get_physmem(pt); // physical memory

	// if free list is empty, need to use fifo to find replacement frame
	if(TAILQ_EMPTY(&free_list_head)){
		// Look at the first element (the head, where we remove) of list2 so we
		// know which frame we are going to use
		struct busy_frame *to_replace;
		to_replace = TAILQ_FIRST(&sbusy_list_head);
		rep_frame = to_replace -> num;

		// insert the frame into list1
		int outframe = sfifo_insert(pt, rep_frame); // the frame to kick out
		// (outframe should be equal to rep_frame)
		if(outframe != rep_frame) printf("OUTFRAME DOESN'T EQUAL REP_FRAME\n");

		// change the page table for the evicted page
		page_table_set_entry(pt, inv_pg_tb[rep_frame], 0, PROT_NONE);
	}	else{
		// there's free frame, get it and insert it into busy lists
		struct free_frame * fitem; // the free frame to use
		fitem = TAILQ_FIRST(&free_list_head);
		TAILQ_REMOVE(&free_list_head, fitem, entries);
		rep_frame = fitem->num;
		free(fitem);
		// insert into busy lists
		sfifo_insert(pt,rep_frame);
	}   

	// read new page from disk into new frame
	disk_read(mydisk, page, &myPM[rep_frame * (PAGE_SIZE)]);
	num_disk_reads++;

	// change page table for current page to the new frame
	page_table_set_entry(pt, page, rep_frame, PROT_READ);
	inv_pg_tb[rep_frame] = page;

	return rep_frame;
}

// insert a page into custom 2 queues return a frame to kick out
// Parameter pt: the page table
// Parameter inframe: the frame to insert into the lists
// Return: the frame kicked out of list2, if any. Otherwise returns -1.
int custom_insert(struct page_table *pt, int inframe)
{
	// insert into list1
	struct busy_frame * bitem;
			// the frame to move to list2 and also the frame to kick out
	struct busy_frame * l1_tail; // the frame to insert into the first queue
	l1_tail = malloc(sizeof(*l1_tail));
	if (l1_tail == NULL) {
		perror("malloc failed");
		exit(EXIT_FAILURE);
	}
	l1_tail -> num = inframe;
	TAILQ_INSERT_TAIL(&busy_list_head, l1_tail, entries);
	// update the busy list info at initialization
	if(l1_len < l1_nframes){
		l1_len ++;
		return -1;
	}
	bitem = TAILQ_FIRST(&busy_list_head);
	TAILQ_REMOVE(&busy_list_head, bitem, entries);

	// Clear bits for frame from list1 to list2
	int midframe; // frame that is being moved from list1 to list2
	midframe = bitem -> num;
	int midpage; // page that is being moved
	midpage = inv_pg_tb[midframe];

	// get current bits for the page
	int frame; // the frame that is being moved
	int bits; // the current bits for the frame being moved
	page_table_get_entry(pt, midpage, &frame, &bits);

	// save wbit table for the second page
	wbit[midpage] = bits;

	// change bits to none, but keep the frame
	page_table_set_entry(pt, midpage, midframe, PROT_NONE);

	// insert into list2
	TAILQ_INSERT_TAIL(&sbusy_list_head, bitem, entries);
	if(l2_len < l2_nframes){
		l2_len ++;
		return -1;
	}
	struct busy_frame * tmp_item;
	int outframe; // the frame to kick out
	for (bitem = TAILQ_FIRST(&sbusy_list_head); bitem != NULL; bitem = tmp_item){
		tmp_item = TAILQ_NEXT(bitem, entries);

		// remove only pages that aren't dirty
		if(wbit[inv_pg_tb[bitem->num]] == PROT_READ){
			// remove the item from list2
			TAILQ_REMOVE(&sbusy_list_head, bitem, entries);
			outframe = bitem->num;
			// set the l1_tail with the replaced frame
			// inframe should be -1 in this case
			l1_tail->num = outframe;
			wbit[inv_pg_tb[outframe]] = PROT_NONE;
			free(bitem);
			return outframe;
		}
	}
	// remove the head of sec queue if every frame is dirty in second queue
	bitem = TAILQ_FIRST(&sbusy_list_head);
	TAILQ_REMOVE(&sbusy_list_head, bitem, entries);
	outframe = bitem -> num;
	// set the l1_tail with the replaced frame, inframe should be -1 in this case
	l1_tail->num = outframe;
	// write to disk for paging out
	char* myPM = page_table_get_physmem(pt); // physical memory
	if (wbit[inv_pg_tb[outframe]] == (PROT_READ|PROT_WRITE)) {
		wrt_cnt ++;
		disk_write(mydisk, inv_pg_tb[outframe], &myPM[outframe * (PAGE_SIZE)]);
	} else printf("disk write failed shouldn't happen");
	wbit[inv_pg_tb[outframe]] = PROT_NONE;
	free(bitem);
	return outframe;
}

// Looks for the page in list2 and if it finds it, reenables bits and puts it
// in list1
// Parameter pt: the page table
// Parameter page: the page to try to find in list2
// Return: if found the page, returns the page itself, else returns -1
int custom_trans_two2one(struct page_table *pt, int page)
{
	struct busy_frame *list2_item; // frame to move, if found
	struct busy_frame *tmp_item; // temp item
	int frame; // the frame to search list2 for
	int bits; // the bits from page_table_get_entry

	page_table_get_entry(pt, page, &frame, &bits);

	for (list2_item = TAILQ_FIRST(&sbusy_list_head); list2_item != NULL;
			list2_item = tmp_item)
	{
		tmp_item = TAILQ_NEXT(list2_item, entries);
		if((frame != 0 && list2_item -> num == frame) ||
				(list2_item->num == 0 && inv_pg_tb[0] == page))
		{
			// remove the item from list2
			TAILQ_REMOVE(&sbusy_list_head, list2_item, entries);
			l2_len --;
			// resume the sec list frame page bits bits
			page_table_set_entry(pt, page, frame, wbit[page]);
			// insert that frame into list1
			custom_insert(pt, frame);
			free(list2_item);
			return(page);
		}
	}

	// if not in list2, return -1
	return(-1);
}

// first looks in list2 and moves to list1 if found, otherwise insert the frame
// into the list1 and if we get a frame out of list2, then we use that to
// replace
// Parameter pt: the page table
// Parameter page: the page that needs a frame
// Return: the frame replaced if we replaced it, otherwise return -1
int custom_replace(struct page_table *pt,int page)
{
	//print_list(); 
	if(custom_trans_two2one(pt, page) >= 0) return(-1);
	//print_list();
	// for the rest of this function, we know that the frame is not in list2

	int rep_frame; // frame to work on, if page is not in second list
	char* myPM = page_table_get_physmem(pt); // physical memory

	// if free list is empty, need to use fifo to find replacement frame
	if(TAILQ_EMPTY(&free_list_head)){
		// Look at the first element (the head, where we remove) of list2 so we
		// know which frame we are going to use
		rep_frame = custom_insert(pt, -1);
		
		// change the page table for the evicted page
		page_table_set_entry(pt, inv_pg_tb[rep_frame], 0, PROT_NONE);
	} else{
		// there's free frame, get it and insert it into busy lists
		struct free_frame * fitem; // the free frame to use
		fitem = TAILQ_FIRST(&free_list_head);
		TAILQ_REMOVE(&free_list_head, fitem, entries);
		rep_frame = fitem->num;
		free(fitem);
		// insert into busy lists
		//print_list();
		custom_insert(pt,rep_frame);
		//print_list();
	}   

	// read new page from disk into new frame
	disk_read(mydisk, page, &myPM[rep_frame * (PAGE_SIZE)]);
	num_disk_reads++;

	// change page table for current page to the new frame
	page_table_set_entry(pt, page, rep_frame, PROT_READ);
	inv_pg_tb[rep_frame] = page;

	return rep_frame;
}

// a random algorithm to replace a frame
// Parameter pt: the page table
// Parameter page: the page we need a frame for
// Return: the frame replaced
int rand_replace( struct page_table *pt,int page)
{
	int rep_frame; // frame to work on

	char* myPM = page_table_get_physmem(pt); // physical memory

	if(TAILQ_EMPTY(&free_list_head)){
		int nfrm; // the number of frames

		nfrm = page_table_get_nframes(pt); 
		rep_frame = lrand48() % nfrm;

		// Check the bits for page to kick out
		int rep_bits; // the bits for the frame to replace
		page_table_get_entry(pt, inv_pg_tb[rep_frame], &rep_frame, &rep_bits);

		// write page to disk if dirty
		if(rep_bits == (PROT_READ|PROT_WRITE)) {
			wrt_cnt ++ ;
			disk_write(mydisk, inv_pg_tb[rep_frame], &myPM[rep_frame * (PAGE_SIZE)]);
		}

		// change the page table for the evicted page
		page_table_set_entry(pt, inv_pg_tb[rep_frame], 0, PROT_NONE);
	} else{
		// there's free frame, get it and use for the page we want to read-in
		struct free_frame * item; // the free frame to use
		item = TAILQ_FIRST(&free_list_head);
		TAILQ_REMOVE(&free_list_head, item, entries);
		rep_frame = item->num;
		free(item);
	}

	// read new page from disk into new frame
	disk_read(mydisk, page, &myPM[rep_frame * (PAGE_SIZE)]);
	num_disk_reads++;

	// change page table for current page to the new frame
	page_table_set_entry(pt, page, rep_frame, PROT_READ);
	inv_pg_tb[rep_frame] = page;

	return rep_frame;
}

//*****************************PAGE FAULT HANDLER*****************************

// Our page fault handler that handles a page fault for given page
// Parameter pt: the page table
// Parameter page: the page that faulted
void page_fault_handler( struct page_table *pt, int page )
{
	num_page_faults++;

	int curFrm; // the frame of the page that faulted
	int curbits; // the bits for the frame that faulted

	// Get curFrm and curbits associated with the page
	page_table_get_entry(pt,page,&curFrm,&curbits);

	// if bits are read, make write and return
	if(curbits == PROT_READ ){
		page_table_set_entry(pt, page, curFrm, PROT_READ|PROT_WRITE);
		return ;
	}
	// if bits are none, then we need to put page in memory
	if(curbits == PROT_NONE ){
		int x = replace_func(pt, page); // the frame that was replaced
		x=x;
	}
	else {
		printf("AT PAGE_FAULT: CURBITS ISN'T PROT_READ OR PROT_NONE\n");
	}
	return;
}

//************************************MAIN************************************

// The main function for the program that reads the command line and runs a
// program based on the arguments
// Parameter argc: the number of command line arguments
// Parameter argv: an array of the command line arguments
// Return: the exit code for the program
int main( int argc, char *argv[] )
{
	if(argc!=5) {
		printf("use: virtmem <npages> <nframes> <rand|fifo|custom> "
				"<sort|scan|focus>\n");
		return 1;
	}

	// initialization
	int npages = atoi(argv[1]); // the number of pages to have
	int nframes = atoi(argv[2]); // the number of frames to have

	inv_pg_tb = malloc(nframes*sizeof(int));
	char rand[] = "rand"; // "rand" string
	char fifo[] = "fifo"; // "fifo" string
	char sfifo[] = "2fifo"; // "2fifo" string
	char cust[] = "custom"; // "custom" string

	struct free_frame * item; // free frames to put into the free list
	TAILQ_INIT(&free_list_head);
	TAILQ_INIT(&busy_list_head);
	TAILQ_INIT(&sbusy_list_head);
	// initialize the free list
	int i; // iteration variable
	for( i = 0 ; i< nframes; i++){
		item = malloc(sizeof(*item));
		if (item == NULL) {
			perror("malloc failed");
			exit(EXIT_FAILURE);
		}

		item -> num = i;
		TAILQ_INSERT_TAIL(&free_list_head, item, entries);
	}

	// Assign replacement policy and initialize values
	if(!strcmp(argv[3], rand)){
		// assign rand replacement policy, replace is a pointer to the function
		srand48(1); // set seed, only want to set it once
		replace_func = rand_replace;
	}else if(!strcmp(argv[3], fifo)){
		replace_func = fifo_replace;	
	}else if(!strcmp(argv[3], sfifo)){
		replace_func = sfifo_replace;
		l2_nframes = (int)(nframes * (SFIFO_RATIO));
		l1_nframes = (nframes - l2_nframes);
		l1_len = 0;
		l2_len = 0;
		wbit = malloc(npages*sizeof(int));
		// set all entries in wbit to 0
		for(i = 0; i < npages; i++) {
			wbit[i] = PROT_NONE;
		}
	}else if(!strcmp(argv[3], cust)) {
	        replace_func = custom_replace;
		l2_nframes = (int)(nframes * (CUSTOM_RATIO));
		l1_nframes = (nframes - l2_nframes);
		l1_len = 0;
		l2_len = 0;
		wbit = malloc(npages*sizeof(int));
		// set all entries in wbit to 0
		for(i = 0; i < npages; i++) {
			wbit[i] = PROT_NONE;
		}
	} else {
		fprintf(stderr,"unknown replacement policy: %s\n",argv[3]);
		free(wbit);
		return 1;
	}

	const char *program = argv[4]; // the program to run

	mydisk = disk_open("myvirtualdisk",npages);
	if(!mydisk) {
		fprintf(stderr,"couldn't create virtual disk: %s\n",strerror(errno));
		return 1;
	}


	struct page_table *pt = page_table_create(npages,nframes,page_fault_handler);
			// the page table
	if(!pt) {
		fprintf(stderr,"couldn't create page table: %s\n",strerror(errno));
		return 1;
	}

	char *virtmem = page_table_get_virtmem(pt); // virtual memory

	if(!strcmp(program,"sort")) {
		sort_program(virtmem,npages*PAGE_SIZE);

	} else if(!strcmp(program,"scan")) {
		scan_program(virtmem,npages*PAGE_SIZE);

	} else if(!strcmp(program,"focus")) {
		focus_program(virtmem,npages*PAGE_SIZE);

	} else {
		fprintf(stderr,"unknown program: %s\n",argv[3]);
		page_table_delete(pt);
		disk_close(mydisk);
		free(wbit);
		return 1;
	}

	// Print page fault, read, and write counts
	//printf("Page Faults: %d\n", num_page_faults);
	//printf("Disk Reads: %d\n", num_disk_reads);
	//printf("Disk Writes: %d\n", wrt_cnt);

	// free memory and close files
	page_table_delete(pt);
	disk_close(mydisk);
	free(wbit);
	return 0;
}
